Ricerca ad albero Monte Carlo

Ricerca ad albero Monte Carlo
Le quattro fasi dell'algoritmo
Classe	algoritmo di ordinamento
Struttura dati	Grafo
Manuale

La ricerca ad albero Monte Carlo (nota anche come MCTS, acronimo dell'inglese Monte Carlo tree search) è un algoritmo di ricerca euristica sviluppato per la ricerca in alberi di decisione, che ha applicazione nella soluzione di giochi da tavolo.

L'algoritmo venne introdotto nel 2006 per il gioco del go^[1] ed è stato in seguito applicato ad altri giochi ad informazione perfetta come scacchi e Shōgi,^[2] a giochi ad informazione incompleta come bridge^[3] e poker,^[4] e a videogiochi di strategia a turni come Total War: Rome II.^[5]

MCTS opera espandendo l'albero di ricerca delle mosse più promettenti tramite campionamento casuale dello spazio di ricerca usando il metodo Monte Carlo. La ricerca si basa sull'esecuzione di numerosi playout (o rollout), dove ogni playout consiste nell'esecuzione di un'intera partita a partire dalla posizione corrente, selezionando le mosse a caso. Il risultato della partita è poi usato per pesare le mosse eseguite e il peso determina la probabilità di eseguire la stessa mossa in successivi playout.^{[Troppa sintesi e quindi poca chiarezza. Uso di termini inglesi non può essere evitato?]}